package main.java.indi.zyj.hot100;

import main.java.indi.zyj.hot100.base.ListNode;

public class _21_isPalindrome {
    public boolean isPalindrome(ListNode head) {


        if (head == null) {
            return true;
        }

        ListNode halfEnd = fistHalfWithEnd(head);
        ListNode halfEndAddOne = reverseList(halfEnd.next);

        ListNode p1 = head, p2 = halfEndAddOne;
        boolean res = true;
        while (res && p2 != null) {
            if (p1.val != p2.val) {
                res = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        // 还原链表并返回结果
        halfEnd.next = reverseList(halfEndAddOne);
        return res;
    }



    private ListNode fistHalfWithEnd(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode reverseList(ListNode head) {

        ListNode  p, q;
        ListNode top = new ListNode(0);
        p = head;

        while (p != null) {
            q = p;
            p = p.next;
            q.next = top.next;
            top.next = q;
        }

        return top.next;

    }
}
